Ein ungerichteter Graph ohne Mehrfachkanten heißt in der Graphentheorie Wald, wenn er keinen nicht-trivialen Kreis enthält. Ist der Graph zudem zusammenhängend, so bezeichnet man ihn Baum. Eine Menge von disjunkten Bäumen bildet also einen Wald.

Ein Knoten in einem Baum heißt Blatt, wenn er Grad 1 besitzt, d.h. ca. mit einem anderen Knoten durch eine Kante verbunden ist. Entsprechend heißt ein Knoten in einem Baum innerer Knoten, wenn er kein Blatt ist. Häufig wird dabei ein Blatt als Wurzel ausgezeichnet.

Ein Teilgraph eines ungerichteten Graphen G=(V,E) heißt spannender Baum von G, wenn er Baum ist und alle Knoten von G enthält.

Ein spannender Baum T eines kantengewichteten, ungerichteten Graphen G heißt minimal, wenn kein anderer spannender Baum von G existiert, dessen Summe seiner Kantengewichte kleiner ist, als die Summe der Kantengewichte von T. Häufig kürzt man "minimal spannender Baum" auch mit MST ab.

Ein gerichteter Graph heißt gerichteter Baum, wenn der zugrundeliegende ungerichtete Graph ein Baum ist. Existiert zusätzlich exakt ein Knoten ohne Eingangskanten (also Eingangsgrad ist Null ), so heißt dieser Knoten Wurzel und der Graph Wurzelbaum. Ein Knoten A mit einer Kante nach B heißt Elternknoten oder auch Vater des Sohnes B. Existiert ein gerichteter Weg von einem Knoten C zu einem anderen Knoten D, so heißt D Nachfolger oder Nachkomme von C und C Vorgänger oder Vorfahre von D. Der Teilbaum TB eines Knoten E des gerichteten Baum T besteht aus allen Knoten, die Nachfolger von E sind und allen Kanten von T, die diese Knoten verbinden. Ein Teilbaum ist also eine Teilmenge eines gerichteten Baums, die selber ein gerichteter Baum ist. Ein Wurzelbaum dessen größter vorkommender Ausgangsgrad q ist, heißt q-närer (Wurzel-)Baum - i. B. binärer Baum.

1. Ein ungerichteter Graph mit endlich vielen Knoten ist exakt dann Baum, wenn er zusammenhängend ist und exakt |V|-1 Kanten enthält.
2. Ein Graph ist exakt dann zusammenhängend, wenn er einen spannenden Baum enthält.
3. Jeder Baum ist bipartit und planar.
4. Zwischen zwei Knoten eines Baumes gibt es exakt einen Pfad.
5. Ein Baum wird zerstörrt durch einfügen einer beliebigen Kante zwischen zwei nicht adjazenten Knoten. Es entsteht ein Kreis.
6. Jeder Knoten des Baumes ist für den Zusammenhang notwendig.

Mittels Tiefensuche kann leicht ein linearer Algorithmus implementiert werden, der zu einem zusammenhängenden Graphen G=(V,E) einen spannenden Baum berechnet.

Zum finden eines minimal spannenden Baumes gibt es den Algorithmus von Kruskal, der Worst-Case-Laufzeit O(|E|ln(|V|)+|V|) besitzt. Etwas schneller ist der Algorithmus von Prim, der Worst-Case-Laufzeit O(|V|ln(|V|)+|E|) besitzt. Dieser benötigt aber mit Fibonacci-Heaps eine recht komplexe Datenstruktur. Man kann zeigen, dass der Algorithmus von Prim damit in dem wesentlichen bestmöglich ist, da man mit seiner Hilfe auch Zahlen sortieren kann.

Wälder und Bäume sind azyklische Graphen und können daher topologisch sortiert werden, siehe Topologisches Sortieren.

Die Berechnung minimal spannender Bäume findet direkte Anwendungen in der Praxis, wenn man zu dem Beispiel kostengünstig zusammenhängende Netzwerke herstellen will.

In der Graphentheorie selbst sind MST-Algorithmen häufig Grundlage komplexerer Algorithmen für schwierigere Probleme. Die Berechnung minimal spannender Bäume ist zu dem Beispiel Bestandteil von Approximations-Algorithmen für das Steinerbaum-Problem oder für das Problem des Handlungsreisenden (oft auch Traveling-Salesman-Problem genannt und TSP abgekürzt).

• Baumstruktur
• Binärbaum
• Dendrogramm
• Baum (Graphentheorie)